class Solution {
public:
    int trap(int A[], int n) {
        if (n<=2) return 0;
        int ret=0;
        int h=1, t=n-2, leftH=A[0], rightH=A[n-1];
        while (h<=t)
            if (leftH<rightH) {
                if (leftH>A[h])
                    ret+=leftH-A[h];
                else
                    leftH=A[h];
                ++h;
            } else {
                if (A[t]<rightH)
                    ret+=rightH-A[t];
                else
                    rightH=A[t];
                --t;
            }
        return ret;
    }
};
